package DP;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/17 11:04
 * @description: 力扣22 括号生成
 */
public class GenrateParenthesis {
    public static void main(String[] args) {

       List<String> res = new ArrayList<>();
       res = new GenrateParenthesis_Solution().generateParenthesis(3);
       for(String x : res){
           System.out.println(x);
       }
    }
}

class GenrateParenthesis_Solution{
    boolean vis[];
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n ==1){
            res.add("()");
            return res;
        }
        vis = new boolean[2*n];
        StringBuffer trace = new StringBuffer();
        char []arr = new char[2*n];
        for(int i = 0;i< n;i++){
            arr[i] = '(';
            arr[2*n-i-1] = ')';
        }
        int index = 0;
        backtrace(res,trace,index,n,arr,vis);
        return res;
    }

    public void backtrace(List<String> res,StringBuffer trace,int index,int n,char []arr,boolean []vis){

        if(index == arr.length && isVaild(trace.toString())){
            res.add(trace.toString());
            return;
        }
        for(int i = 0;i < 2*n;i++){
            if(vis[i] || (i>0 && arr[i-1] == arr[i] && !vis[i-1])){
                continue;
            }
            vis[i] = true;
            trace.append(arr[i]);
            backtrace(res,trace,index+1,n,arr,vis);
            trace.deleteCharAt(index);
            vis[i] = false;

        }
    }
    public boolean isVaild(String s){
        char []arr = s.toCharArray();
        int level = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == '('){
                level++;
            }else {
                level--;
            }
            if(level <0){
                return false;
            }
        }
        if(level != 0){
            return false;
        }
        return true;
    }
}
